package org.example.leetCode;

import java.util.Scanner;
import java.util.Arrays;

/**
 * ACM 模式测试
 */
public class Code0 {
    public static int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int[] tails = new int[nums.length];
        int len = 0;

        for (int num : nums) {
            // 使用二分查找找到插入位置
            int i = Arrays.binarySearch(tails, 0, len, num);
            if (i < 0) {
                i = -(i + 1); // 转换为插入位置
            }
            tails[i] = num;
            if (i == len) {
                len++;
            }
        }

        return len;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        System.out.println(lengthOfLIS(nums));
    }
}

